Forum:Is the Xi function ITTM-computable?
it's vel 06:56, October 4, 2014 (UTC) Algorithm for bounded ranks I believe I have figured out an algorithm which does the following: suppose we are given SKIO tree T and ordinal \(\alpha\) coded in some standard way. Then, if T has rank at most \(\alpha\), we will reduce T and check if it halts. If, however, it turns out that T has higher rank (or doesn't have one) then we will return an error. The algorithm is as follows: *If combinator is S, K or I then reduce in obvious way *If combinator is O and \(\alpha=0\), return error *If combinator is O and \(\alpha>0\), then: **"Guess" the value \(\beta<\alpha\) **Do the whole algorithm for ordinal \(\beta\) and tree T' which is x in oracle query **If subroutine returned "yes", reduce according to y in oracle query **If subroutine returned "no", reduce according to z in oracle query **If subroutine returned an error and not all guesses were used, repeat the above subroutine with different value of \(\beta\) **If subrouting returned an error and we ran out of guesses, return an error *Repeat from the first step *If T has reduced to I, return "yes" *If T reduced to something other than I, or infinitely many reductions were made, return "no" First I'll clarify what "guessing" is - coding of an ordinal induces a mapping \(\omega\mapsto\alpha\), and we actually try out ordinals \(\beta\) one-by-one with help of this mapping. Now we have to check that this algorithm is sound and always terminates. We do this by transfinite recursion on \(\alpha\). If \(\alpha=0\), then if rank of tree is \(>0\), we must have made oracle query. But second step tells us that it will then return an error. If no queries were made, then we simply simulate S, K, I combinators to see if it returns I. If \(\alpha>0\), then, if oracle query happens, we will have to make at most \(\omega\) guesses, and for each of them subroutine terminates (from inductive assumption), and we have at most \(\omega\) steps of whole reduction to make. ITTM is capable of this. Now, if tree has rank at most \(\alpha\), then each of its queried trees will have rank less than \(\alpha\), so some guesses \(\beta\) will "get it right", and will return sound result (ind. assumption). If however tree has rank \(>\alpha\), one of its queries will have rank \(\geq\alpha\), so no guess will be able to "get it right". Thus we will constantly get an error, and when we run out of guesses, we will return an error. So the algorithm is sound. Now suppose we have ordinal \(\alpha\) which is upper bound of possible ranks of SKIO tree. Then putting any well-founded tree into algorithm along with \(\alpha\) will give us the result. If tree is ill-founded, we will still get an error. So, given this ordinal \(\alpha\), we can even solve the problem of well-foundedness. Thus we can compute Xi function by sieving out ill-founded and non-terminating trees. Thanks to this algorithm, only thing which we now have to figure out is the size of this ordinal \(\alpha\). If it's writable, we are home. LittlePeng9 (talk) 19:40, October 4, 2014 (UTC) Trees with ranks up to CK ordinal Deedlit has asked me for this, so I'll show here that \(\omega_1^\text{CK}\) is a lower bound on supremum of possible ranks. My argument shows the following: for every Turing machine coding a well-order of order type \(\alpha\), we can find an SKIO tree of rank \(\alpha\). Induction base is at 0, this is quite trivial. We can just map machine coding 0 to any SKI tree. Suppose we are given Turing machine \(T\) which codes a well-order \(\prec\) on \(\Bbb N\) of order type \(\alpha\). Now we let \(T_n\) be a similar machine, except that it "skips" over the numbers which are \(\prec\)-greater than \(n\). We can make it so that it actually codes a well-order. Now here is an important thing: \(T_n\) can be computed from description of \(T\) and \(n\). I'm not going to go into details of such computation, but it's relatively easy to see. Now, another point - if in \(T\) ordering number \(n\) represents ordinal \(\alpha_n\), then machine \(T_n\) codes ordinal \(\alpha_n\). It's again quite easy to realize. So, when we go through all \(n\), machines \(T_n\) will code all possible ordinals \(<\alpha\). Now we are getting to trees - we set up a tree, based on description of \(T\), which first computes descriptions of machine \(T_0\), constructs corresponding tree of rank \(\alpha_0\) (by transfinite induction), and then apply oracle combinator to this tree. Then we do the same thing for \(T_1\) and \(\alpha_1\), \(T_2\) and \(\alpha_2\) and so on. Note that oracle combinator is applied only to trees previously built by transfinite induction, so by parallel such argument we can see that everything else can be done with SKI combinators alone. So the rank of resulting tree is the least ordinal greater than all \(\alpha_n\), which is exactly \(\alpha\), so this is our rank of the tree. Because Turing machines can code orderings of any order type \(<\omega_1^\text{CK}\) we get that there are trees of any recursive rank. LittlePeng9 (talk) 20:31, October 8, 2014 (UTC) :Thanks, Wojowu. Forgive my SKIO ignorance, but how do you create a finite tree that applies oracle combinators to infinitely many trees? Deedlit11 (talk) 21:54, October 8, 2014 (UTC) ::To be honest, I have no idea. This is one of these things where you just have to believe that, since the construction I gave doesn't require anything stronger than TM, we can also make an SKI tree which will do the thing for us. This is why I remarked that \(T_n\) is computable by \(T\) and \(n\). LittlePeng9 (talk) 05:01, October 9, 2014 (UTC) Upper bound of complexity of SKIO I was able to show that SKIO calculus is \(\Delta^1_2\), from which it follows that they are computable by Koepke's ordinal Turing machines (OTMs). To be precise, the problem "given SKIO tree T, does it reduce to some irreducible tree?" can be equivalently stated "there exists ordinal \(\alpha\) such that algorithm on the beginning, ran on input T and \(\alpha\), halts with the tree in irreducible form". Because the algorithm is executible on ITTM, then problem of asking if it returns given answer is \(\Delta_2^1\) problem, by one result of Hamkins & Lewis. So question if there exists an ordinal such that this holds is \(\Sigma_2^1\). Alternatively, we can say that tree becomes irreducible if "for every ordinal \(\alpha\), either the algorithm returns that tree didn't reduce, or returns an error when running on input \(\alpha\), T". This in turn is \(\Pi_2^1\) statement. So question of T reducing to some irreducible form is in \(\Sigma_2^1\cap\Pi_2^1=\Delta_2^1\). Thus, by a result of (I believe) Koepke, which states that OTM-decidable problems are exactly \(\Delta_2^1\) problems, we get that OTMs can determine if SKIO tree has a normal form or not. As a corollary, Xi function is OTM computable. LittlePeng9 (talk) 05:37, October 11, 2014 (UTC) : Okay, a simplier proof: we can modify algorithm from the beginning so that we won't be working with ordinal coded as a real, but rather we will work with a single marking far on the ordinal tape. So, for example, if we are given tree T and ordinal \(\omega^2\), we just have tree T written as usual and a single marking on square number \(\omega^2\). When we are running a subroutine, we have to copy the ordinal, but this isn't that hard - we can from the beginning code the tree on every second cell of the tape, then we can use empty squares to know how big the ordinal is and copy it. The problem of trying out all smaller ranks also simplifies - we can just try out transfinitely many of them, one by one. And now, we can just try out all possible initial ordinals looking for the rank of tree T. This only works for trees which are well-founded, because we won't find an answer when tree doesn't have a rank. Thankfully, first proof seems to still be flawless. LittlePeng9 (talk) 05:57, October 11, 2014 (UTC) Lower bound of complexity of SKIOO2 Okay, this time it's not about SKIO, but about SKIOO2 - it's not hyperarithmetical. Recall that the problem of deciding if a Turing machine codes a well-order is an \(\Pi_1^1\)-complete problem (it follows that it's not \(\Sigma_1^1\) and thus not \(\Delta_1^1\), which is class of hyperarithmetical things). For a given TM, we will build an SKIO tree T which is well-founded iff TM indeed codes a well-order. T will work in "turns" - on odd-numbered turns, it will check if TM codes a total order - it's a simple syntactic property to prove, if it happens to fail, we will force our tree into an ill-founded one - if P is paradoxal combinator, we will just ask oracle about it. Now, on even numbered turns, we will try to build an infinite descending sequence. We will keep checking for pairs \((a_1,a_2)\) to see if \(a_1\succ a_2\) in ordering induced by machine. If we find such pair, then we create a similar subtree (described in next sentence) and apply oracle combinator to it, and then continue looking for such pairs. The new tree will check for pairs \((a_2,a_3)\) with \(a_2\succ a_3\), and if it finds one, it will repeat the construction and application. Now I claim that the resulting SKIO tree is well-founded (has rank) iff the ordering which the TM gives is well-order. Suppose that the ordering isn't well. Then we can actually find an infinite descending sequence \(a_1\succ a_2\succ...\), so we can find an infinite series of nested oracle queries. If the tree had a rank, then every queried tree would have a rank too, and they would have smaller ranks. Indeed, they would form a decreasing sequence of ordinals, but it cannot be infinite. So the tree is ill-founded. Now suppose that the tree is ill-founded. Thus it doesn't have a rank. If all of its queried trees had ranks, then it would itself have a rank which is impossible. So, for some pair \(a_1\succ a_2\) it makes a query which is ill-founded. So the queried tree doesn't have a rank either, so for some pair \(a_2\succ a_3\) it would make an ill-founded query, and so on. This forms an infinite descending sequence \(a_1\succ a_2\succ a_3\succ...\), thus the ordering induced by machine isn't well. So, because by definition of \(\Omega_2\) combinator it can resolve the question of well-foundedness of a tree, it's not hyperarithmetical, and we can deduce that it can solve all problems in \(\Sigma_1^1\cup\Pi_1^1\). LittlePeng9 (talk) 11:26, October 11, 2014 (UTC) Here is an attempt to construct an SKIOO2 tree of rank \(\omega_1^\text{CK}\) and no lower. I'll remark that, when calculating a rank, I don't take into consideration queries made by \(\Omega_2\) combinator, because then it gives us no power because queries to ill-founded trees would be ill-founded. I'm not entirely sure if this is right, but here we go: first, note that my construction in second section can be executed by a TM. So we can set up a single tree which, for every TM, first checks if the order it codes is well, using construction above, and if it is, then we can use the construction from second section to make tree of rank being ordinal which that machine codes, and then makes \(\Omega\) query for that tree. This way, the resulting tree will have rank at least as high as any ordinal which TM can code, that is - \(\omega_1^\text{CK}\). LittlePeng9 (talk) 19:32, October 12, 2014 (UTC) : I'm not sure, but I think that the fact that we can effectively compute well-order of order type CK, as well as solve any \(\Pi_1^1\) problem, is enough to prove that we can have trees of ranks up to \(\omega_2^\text{CK}\). LittlePeng9 (talk) 19:34, October 12, 2014 (UTC) ::Perhaps the best way to show that is to use Sacks' result that the supremum of ordinals codeable by an oracle Turing machine is always an admissible ordinal (Did I state that right?). So with an oracle for \(\omega_\alpha^\text{CK}\), we can code all ordinals up to \(\omega_{\alpha+1}^\text{CK}\). However, I'm not sure how to convert from "we can code ordinal \(\alpha\)" to "there exists a tree of rank \(\alpha\)". ::Assuming your arguments are correct, it seems then that with an \(\Omega_3\) combinator can can make a tree of rank \(\omega_2^\text{CK}\), by a similar argument. Then if we can argue that the limit of any oracle combinator system must be an admissible ordinal, then we know that SKIOO2O3 must be able to construct all trees of rank up to \(\omega_3^\text{CK}\). Similarly, we would have that with oracle combinator \(\Omega_\alpha\), we can construct trees with all ranks up to \(\omega_\alpha^\text{CK}\). Deedlit11 (talk) 20:15, October 12, 2014 (UTC) :::I believe this is indeed correct. Below I explain this in a bit more detail. LittlePeng9 (talk) 20:33, October 12, 2014 (UTC) Okay, this is a bit of work around, but I'm not a specialist in \(\alpha\)- recursion theory, and I don't know what's obvious and what isn't there :P Suppose that we have an oracle Turing machine with access to oracle A saying which SKIO trees are well founded and which are not. As we have seen in section above, this is enough to decide if a TM codes a well-ordering. With similar trick as there, we can make a machine which codes well-ordering of order type CK. Let us list all the TMs which code a well-order. Then we make the following ordering: \((a,b)\prec(c,d)\) if \(a2 is at least as strong as oracle A, we can actually compute that oracle and, by construction similar to one in second section, I believe that we can build trees of any rank below \(\omega_2^\text{CK}\). LittlePeng9 (talk) 20:33, October 12, 2014 (UTC) Problem solved A couple of days ago I've managed to answer the question in positive - Goucher's xi function is ITTM-computable. This follows from the algorithm for bounded ranks as soon as we prove that the ranks are bounded by \(\omega_1^\mathrm{CK}\). This bound follows from the following three facts. Fix some well-founded SKIO combinator. *Using a straightforward way of encoding SKIO reductions which includes reductions of all the oracle-called combinators, let \(C\) be the encoding of reduction of the combinator. Then \(\{C\}\) is \(\Sigma^1_1\) (indeed, it's something like \(\Pi^0_2\)). This is because the encoding is characterized by the fact that all the steps are valid, which most importantly includes checking that, upon an oracle call, the halting judgement is valid, and this can be encoded in an arithmetical formula. *Gandy basis theorem (theorem 2.9 in this paper) tells us that any nonempty \(\Sigma^1_1\) set contains an element \(A\) such that every ordinal computable from \(A\) is computable. Applying this to \(\{C\}\), every ordinal computable from \(C\) is computable. *The rank of the combinator is upper-bounded by an ordinal computable from \(C\). This follows almost immediately from the fact that the of a tree is computable from the tree and, when the tree is well-founded, it's a well-order of length at least the rank of the tree. Applying this to the tree built from oracle calls, which is well-founded since we assume the combinator is, we get the bound. Clearly, the above imply the rank of a well-founded SKIO tree is computable. By the way, I have also that the method of the last section above can be generalized to compute iterated hyperjumps, so the upper bound for the ranks of SKIOO2 combinators seems to be a decently large countable ordinal - my guess is the first recursively inaccessible ordinal. From there, my wild guess is that for SKI augmented by n+1 oracle combinators the ordinal is going to be the first recursively n-inaccessible ordinal. As of now I am unable to prove any of that though. There appears to be quite some literature about computability from functionals which remind me of the oracles in how they can, in a way, apply the functionals to themselves, and the methods used there might be applicable here, but I don't have enough time to work on that. Maybe one day someone else will pick up on that. As a teaser, the results from there suggest that if we were to introduce transfinite oracles, and then an oracle whose order would depend on a rank of a combinator it has as an input, then the ordinals computable would go up to the least \(\alpha\) which is recursively \(\alpha\)-inaccessible (i.e. recursively hyperinaccessible). Also, if all those ordinals are even close to being correct, then all of the functions are ITTM-computable, so that's a nice result. LittlePeng9 (talk) 16:23, February 2, 2018 (UTC)